package lc_面试题_17_06_2出现的次数;

import java.util.Arrays;

public class Solution {
	public int numberOf2sInRange(int n) {
		int[] array = String.valueOf(n).chars().map(a -> a - '0').toArray();
		Integer[][][] dp = new Integer[array.length][2][array.length];
		return f(array, 0, 1, 0, dp);
	}

	private int f(int[] n, int index, int ceil, int cnt, Integer[][][] dp) {
		if (index == n.length) {
			return cnt;
		}
		if (dp[index][ceil][cnt] != null) {
			return dp[index][ceil][cnt];
		}
		int up = ceil == 1 ? n[index] : 9;
		int ans = 0;
		for (int i = 0; i <= up; i++) {
			ans += f(n, index + 1, ceil == 1 && i == up ? 1 : 0, cnt + (i == 2 ? 1 : 0), dp);
		}
		dp[index][ceil][cnt] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		System.out.println(so.numberOf2sInRange(25));
	}
}